package com.ocean.divideandconquer.medium;

import com.ocean.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/03/01 <br>
 */
public class ConstructBinaryTree2 {

    private Map<Integer, Integer> map = new HashMap<>();

    private int[] inorder;
    private int[] postorder;
    private int rootIdx;

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        this.inorder = inorder;
        this.postorder = postorder;
        this.rootIdx = postorder.length - 1;
        return buildTreeRec(0, inorder.length - 1);
    }


    /**
     * 中序遍历：
     * 【{左子树中序遍历} 根节点 {右子树中序遍历}】
     * 后续遍历：
     * 【{左子树后续遍历}{右子树的后续遍历}根节点】
     */
    public TreeNode buildTreeRec(int leftIdx, int rightIdx) {
        if (leftIdx > rightIdx) {
            return null;
        }
        int rootVal = postorder[rootIdx];
        TreeNode root = new TreeNode(rootVal);
        rootIdx--;
        Integer index = map.get(rootVal);
        root.right = buildTreeRec(index + 1, rightIdx);
        root.left = buildTreeRec(leftIdx, index - 1);
        return root;
    }
}
